package Leetcode2.链表.graph;

/**
 * 岛屿的周长  row x col
 */
public class Algo463 {
    public static int islandPerimeter(int[][] grid) {
        int  colLength = grid[0].length;
        int rowLength = grid.length;
        int[][] copy = new int[rowLength+2][colLength+2];
        for (int i = 1; i < copy.length-1; i++) {
            for (int j = 1; j < copy[i].length-1; j++) {
                copy[i][j] = grid[i-1][j-1];
            }
        }

        int result= 0;
        for (int i = 1; i < copy.length-1; i++) {
            for (int j = 1; j < copy[i].length-1; j++) {
                if(copy[i][j] == 1) {
                    int up = i-1;
                    int down = i+1;
                    int left = j - 1;
                    int right = j+1;
                    if(copy[up][j] == 0) {
                        result++;
                    }
                    if(copy[down][j] == 0) {
                        result++;
                    }
                    if(copy[i][left] == 0) {
                        result++;
                    }
                    if(copy[i][right] == 0) {
                        result++;
                    }
                }
            }
        }
        return result;
    }

    public static int numIslands(char[][] grid) {
        int rowLength = grid.length;
        int colLength = grid[0].length;
        boolean[][] visited = new boolean[rowLength][colLength];

        char[][] copy = new char[rowLength+2][colLength+2];
        for (int i = 0; i < copy.length; i++) {
            for (int j = 0; j < copy[i].length; j++) {
                if(i == 0 || j == 0 || i == copy.length-1 || j == copy[i].length-1) {
                    copy[i][j] = '0';
                }else {
                    copy[i][j] = grid[i-1][j-1];
                }
            }
        }

        int result = 0;
        for (int i = 1; i < copy.length-1; i++) {
            for (int j = 1; j < copy[i].length-1; j++) {
                if(copy[i][j] == '1') {
                    int up = i-1;
                    int left = j - 1;
                    if(copy[up][j] == '0' && copy[i][left] == '0') {
                        result++;
                    }
                    if(copy[up][j] == '1' && copy[i][left] == '1' && copy[up][left] == '0' && result>1) {
                        result--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        char[][] arr =  {{'1','0','1','1','1'},
                {'1','0','1','0','1'},
                {'1','1','1','0','1'}};
        System.out.println(numIslands2(arr));
    }

    private static int numIslands2(char[][] arr) {
        int row = arr.length;  //多少行
        int col = arr[0].length; //多少列

        int result = 0;
        //广度优先遍历
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(arr[i][j] == '0') {
                    continue;
                }
                result++;
                arr[i][j] = '0';
                traverse(arr, i, j);
            }
        }

        return result;
    }

    private static void traverse(char[][] arr, int i, int j) {
        int down = i+1;
        int right = j+1;
        int left = j-1;
        int up = i-1;
        if(up>=0 && arr[up][j] == '1') {
            arr[up][j] = '0';
            traverse(arr, up, j);
        }
        if(down < arr.length && arr[down][j] == '1' ) {
            arr[down][j] = '0';
            traverse(arr, down, j);
        }
        if(right < arr[0].length && arr[i][right] == '1') {
            arr[i][right] = '0';
            traverse(arr, i, right);
        }
        if(left>=0 && arr[i][left] == '1') {
            arr[i][left] = '0';
            traverse(arr, i, left);
        }
    }
}
